package com.xinwei.leetcode.数组;

import java.util.HashMap;

// https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
public class _167_两数之和Ⅱ输入有序数组 {
    // 复习第一题的做法
    public static int[] twoSum(int[] numbers, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(numbers[0], 0);
        for (int i = 1; i < numbers.length; i++) {
            if (map.containsKey(target - numbers[i])){
                return new int[]{map.get(target - numbers[i]) + 1, i + 1};
            }
            map.put(numbers[i], i);
        }
        return null;
    }

    // 双指针解法
    // 没有用上有序数组的条件，在有序的情况下，设i为左指针，j为右指针：
    // 若num[i] + num[j] > target  则i右移，仍有num[i] + num[j] > target
    // 若num[i] + num[j] < target  则j左移，仍有num[i] + num[j] < target
    // 于是就用上面这个特性，设定左右指针，不断逼近正确值
    // 思考：双指针就往往不会再用for循环
    public static int[] twoSum1(int[] numbers, int target) {
        Integer left = 0;
        Integer right = numbers.length - 1;
        Integer sum = 0;
        while (left < right) {
            sum = numbers[left] + numbers[right];
            if (sum == target) return new int[]{left + 1, right + 1};
            if (sum > target) {
                right--;
                continue;
            }else {
                left++;
                continue;
            }

        }
        return null;
    }
}
